package com.graph;

import com.collection.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class CC {

    public Graph g;
    private int count;
    private int [] id;
    private boolean[] marked;
    public CC (Graph g) {
        this.g = g;
        id = new int[g.V()];
        marked = new boolean[g.V()];
        count = 0;
        for (int i = 0; i < g.V(); i++) {
            if (!marked[i]) {
                count += 1;
                dfs(i);
            }
        }
    }

    public void dfs(int v) {
        if (marked[v]) {
            return;
        }
        marked[v] = true;
        id[v] = count;
        for (Integer i : g.adj(v)) {
            if (!marked[i])
                dfs(i);
        }
    }

    public int id(int v) {
        return id[v];
    }

    public int getCount() {return count;}

    public static void main(String[] args) {

        Graph g = new Graph(new In(args[0]));
        CC cc = new CC(g);
        Bag<Integer>[] components = (Bag<Integer>[]) new Bag[cc.getCount()];
        for (int i = 0; i < cc.getCount(); i++) {
            components[i] = new Bag<>();
        }
        for (int i = 0; i < cc.g.V(); i++) {
            components[cc.id(i) - 1].add(i);
        }
        for (int i = 0; i < cc.getCount(); i++) {
            for (int v : components[i]) {
                StdOut.print(v + " ");
            }
            StdOut.println();
        }
    }


}
